package com.shixianjun.leetcode;

import java.util.HashSet;

public class _160_相交链表 {

    static public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        HashSet<ListNode> cache = new HashSet<>();

        while (headA != null || headB != null) {
            if (headA != null) {
                if (cache.contains(headA)) {
                    return headA;
                } else {
                    cache.add(headA);
                }
                headA = headA.next;
            }

            if (headB != null) {
                if (cache.contains(headB)) {
                    return headB;
                } else {
                    cache.add(headB);
                }
                headB = headB.next;
            }
        }
        return null;
    }

    public static void main(String[] args) {
    }
}
